Infrastructure multihop Wireless Mesh Networks (denoted WMNs hereafter) represent a technology to deploy wireless broadband services in a relatively inexpensive manner. A WMN consists of a collection of geographically-fixed wireless nodes which provide the infrastructure for wireless access to the global Internet over a relatively large geographic area. A WMN can provide wireless services to both fixed residential end-users and to mobile end-users. WMNs are described in a paper by I. Akyildiz et al, “A Survey on Wireless Mesh Networks”, IEEE Radio Communications, pp. S23-S30, September 2005, which is hereby incorporated by reference. Scheduling in WMNs is described in a paper by Min Cao et al, “Multi-Hop Wireless Backhaul Networks: A Cross-Layer Design Paradigm”, IEEE Journal Selected Areas of Communications, Vol. 24, No. 4, May 2007, which is hereby incorporated by reference.
Several wireless network standards exist, including 3G, Long Term Evolution (LTE), the IEEE 802.16 WiMAX standards and the IEEE 802.11 WiFi standards. Resource allocation in mesh networks using the WiMax standard is summarized in the paper by S. Xergias et al, “Centralized Resource Allocation for Multimedia Traffic in IEEE 802.16 Mesh Networks”, Proc. IEEE, Vol. 96, Issue 1, pp. 54-63, 2008, which is hereby incorporated by reference. Extensions of the IEEE 802.11 WiFi Standard to include mesh networking are described in the paper by G. Hiertz et al, entitled “Principles of IEEE 802.11s”, Proc. IEEE Computer Comm. and Networks Conference, 2007, pages 1002-1007 which is hereby incorporated by reference.
Each standard uses a different terminology for similar concepts. The IEEE 802.11 WiFi standard describes a wireless router as an ‘Access Point’, while the IEEE 802.16 WiMax standard describes a wireless router a ‘Base-Station’. In this document a generic model of a WMN network is used, which can use any of several underlying radio technologies. There are 2 types of wireless nodes in a generic WMN model, the Gateway Base-Stations (GS) and regular Base-Stations (BS). A GS has a wired connection to the Internet and acts as a gateway to the Internet. It can represent a WiMAX Base-station with a wired connection to the Internet, or an 802.11 Access Point with a wired connection to the Internet, or a 3G or LTE node with wired access to the Internet. The end-users of the infrastructure will be called Stationary Subscriber Stations (SSSs) such as homes, and Mobile Subscriber Stations (MSSs) such as cell phones. WMNs support two types of traffic, referred to herein as ‘Backhaul’ traffic between the infrastructure nodes, and ‘End-User’ traffic which is delivered directly to/from an end-user. A wireless mesh network that manages both backhaul traffic and end-user traffic is described in U.S. Pat. No. 7,164,667 B2, entitled “Integrated Wireless Distribution and Mesh Backhaul Networks”, January. 2007, which is hereby incorporated by reference. (This patent calls ‘End-User’ traffic the ‘Distribution’ traffic.)
A BS does not have a wired connection to the Internet, and must perform routing or forwarding functions for backhaul traffic, where it receives a packet, determines a suitable outgoing link, and then forwards the packet to another node, either a GS or another BS. The GSs and BSs in the WMN have geographically fixed locations, and are geographically positioned by a service provider to provide high-quality radio link between nodes. The nodes may be positioned to maximize Line-of-Sight communications, or to have good multipath reflection characteristics between large statically positioned objects (ie buildings, bridges, retaining walls) to enable good reception. In an infrastructure WMH the radio links exist between stationary nodes, where the channel degradation found in mobile nodes does not exist. The addition of relay stations and micro-basestations (described ahead) will ensure that all infrastructure radio links have an acceptably high quality. As a result, the quality of infrastructure WMN radio links is very good and will change relatively slowly in time, primarily due to weather or the ionosphere.
A Relay Station (RS) is a simplified BS. It accepts a packet in one time-slot, and typically forwards the packet to another node in a subsequent time-slot. The next node may be a GS, BS, or another RS. In the literature, a RS is often defined between 2 fixed nodes. In our WMN model, a RS can forward packets between 2 dedicated nodes, or it can perform limited routing or forwarding, where it examines a packet header and selects an outgoing link accordingly. In our generic WMN model, a relay station may use radio links which must be scheduled. Relay networks are described in the paper by V. Genc et al, “IEEE 802.16J Relay-Based Wireless Access Networks: An Overview”, IEEE Wireless Communications, October 2008, pp. 56-63, which is hereby incorporated by reference.
The performance of wireless access networks may be improved by shrinking the cell sizes found in traditional systems to create “micro-cells”, “pico-cells” or “femto-cells”. Hierarchical or hybrid WMNs have recently been proposed where conventional Base-Stations are augmented with ‘Micro-Base-Stations’ (mBSs), which operate in smaller micro-cells. These mBSs require less transmit power and can achieve higher data rates to nearby destinations. A mBS may receive packets from a nearby BS, GS or RS, and typically delivers these to end-users which are nearby. It also receives packets from the end-users which are nearby, and delivers these to a nearly BS, GS or RS. A hierarchical WMN with mBSs is described in the paper by Y. Amano, et al, “Laboratory Experiments of TDD/SDMA OFDM Wireless Backhaul in a Downlink for Hierarchical Broadband Wireless Access Systems”, IEEE 2008, which is hereby incorporated by reference. Hybrid WMNs are also described in the paper by S. Zhao et al, “Scalability and Performance Evaluation of Hierarchical Hybrid Wireless Networks”, IEEE Transactions on Networking, to Appear, 2009, which is hereby incorporated by reference.
The nodes (GS, BS, RS, mBS) and the radio links available between these nodes can be used to create a graph model of the infrastructure WMN denoted G(V,E), where V represents the set of nodes, and E represents the set of directed edges. Hereafter, we will not distinguish between Gateway Base-Stations, Base-Stations, Relay-Stations and micro-Base-Stations: They all will be referred to as BSs or nodes. The movement of traffic between BSs is called ‘Backhauling’. Typically, backhauling involves moving relatively large amounts of traffic from the global IP network to the nodes in the WMN, and conversely. In the graph model, a directed wireless link between a pair of nodes is represented by a directed edge in the graph. Edges may be active or inactive in each time-slot. An edge must be assigned a ‘radio channel’ if it is active. A ‘radio channel’ utilizes some amount of the frequency spectrum in the physical neighborhood of the active edge. To move large amounts of backhaul traffic between the nodes in a WMN efficiently, the transmission of the traffic between the nodes in a WMN may be scheduled in a TDMA scheduling frame, and the active edges must be assigned non-conflicting radio channels.
Multiple Access Techniques
Radio systems typically use three different techniques to enable multiple users to access a shared medium, Time Division Multiple Access (TDMA), Frequency Division Multiple Access (FDMA), and Code Division Multiple Access (CDMA). More recently, Space Division Multiple Access (SDMA) has become feasible. The concepts of TDMA, OFDMA, CDMA and SDMA are described in the paper by I. Koutsopoulos et al, “The Impact of Space Division Multiplexing on Resource Allocation: A Unified Treatment of TDMA, OFDMA and CDMA”, IEEE transactions on Communications, Vol. 56, No. 2, February 2008, which is hereby incorporated by reference.
In a TDMA system, the time axis is divided into time-slots, where a time-slot has sufficient duration to allow a fixed-sized packet to be transferred between two nodes over a radio channel. The IEEE 802.16 WiMax standard and the IEEE 802.11a/g/n WiFi standard use a subclass of FDMA called Orthogonal FDMA or OFDMA. In the OFDMA technology, the wide-band frequency spectrum is divided into many narrow-band subcarriers, which are substantially orthogonal since they are appropriately spaced. Typically, the subcarriers can be grouped into multiple logical orthogonal radio ‘sub-channels’. Multiple sub-channels can be assigned to multiple users, thereby allowing multiple access in the frequency domain. The OFDMA technology is summarized in an article by S. Srikanth et al, “Orthogonal Frequency Division Multiple Access: Is it the Multiple Access System of the Future”, AU-KBC Research Center, Anna University, Chennai, India, which is hereby incorporated by reference.
According to the paper by Srikanth et al, an OFDMA system may partition a wide-band spectrum into 1680 narrow-band subcarriers, which can be grouped into 24 orthogonal radio sub-channels with 70 subcarriers each. These 24 sub-channels can be allocated to a single user or to multiple (up to 24) distinct users. The sub-channels may have substantially the same capacity and are relatively orthogonal and are relatively free of interference. In a combined TDMA/OFDMA system, multiple users can transmit over multiple orthogonal logical sub-channels in the same time-slot. In a wireless network using TDMA/FDMA or TDMA/OFDMA, the network model G(V,E) has distinct features. A node may have up to K radio transmitter/receiver modules (transceivers), allowing it to access up to K distinct OFDMA radio sub-channels in each time-slot.
In a CDMA system, each node multiplies every bit in its bit-stream by a fixed bit-sequence (code) before transmission. The net affect is that the transmission from one node is spread with relatively low power over a wide frequency range. A receiving node correlates its received signal with the same code to extract the transmission. Codes are chosen to be substantially orthogonal, so that the correlation of any two different codes yields noise which can be filtered. In a combined TDMA/CDMA system, multiple users can transmit over multiple orthogonal CDMA channels in one time-slot. A node may have up to K transceivers, allowing it to access up to K substantially orthogonal CDMA radio channels in each time-slot.
Recently, Space Division Multiple Access (SDMA) has emerged as a feasible technology. In a SDMA system, Directional Antennae systems are used. A transmitting or receiving node may utilize multiple antennas in an ‘antenna array’. A transmitting node may use beamforming algorithms to direct its transmissions along a particular direction. The antenna weights must be precomputed given the preferred direction and the number of antennas. Similarly, a receiving node may use beamforming algorithms to focus its receptions along a particular direction and to null out interference.
Recently, Multiple Input Multiple Output (MIMO) technologies have been developed. In a MIMO Directional Antenna system, each transmitter and each receiver have an antenna array. MIMO has the potential to offer significant increases in wireless system performance. MIMO technologies can support spatial reuse, where the same radio channel can be reused to support multiple transmissions between different pairs of nodes in the same physical region. To achieve the SDMA, both the transmitters and receivers must precompute antennae weights to strengthen the preferred signal, and to weaken the unwanted signals. A prerequisite to achieving the full potential of MIMO technologies in a WMN is that the pairs of communication nodes are identified in advance, allowing for the precomputation of transmission powers and antenna weights for all the communicating nodes. An algorithm for precomputing the antenna parameters for MIMO technology in a WMN are described in the paper by Min Cao referenced earlier.
End-User Traffic Delivery
The delivery of packets from the infrastructure nodes to the end-users over the last hop (both the uplink and downlink) must be included into the above infrastructure WMN model. The traffic involving the ultimate end-users will be called ‘End-User’ traffic. It is often called “Point-to-Multipoint” traffic in the literature. In our network model, the end-users are called the Mobile Subscriber Stations (MSSs) and Stationary Subscriber Stations (SSSs). Hereafter, both types of end-users will also be denoted as ‘Subscriber Stations’ (SSs). The uplink and downlink wireless communication channels between BSs and end-users can be represented by a 2nd class of radio edge in the network model G(V,E). The quality of these edges may be transient due to the effects of end-user mobility. When communicating with a mobile end-user in system using TDMA, a BS may use Opportunistic Scheduling or Channel-Aware scheduling, where a mobile end-user is typically selected for communications in a time-slot based upon the recent radio channel quality. In a particular time-slot, the communications may be enabled to mobile end-users whose radio channel quality is high and above the recent average channel quality. Channel-aware scheduling is described in a paper by A. Iera et al, entitled “Channel-Aware QoS and Fairness Provisioning in IEEE 802.16/WiMAX Broadband Wireless Access Systems”, IEEE Network, September/October 2007, which is hereby incorporated by reference.
End-user traffic can be scheduled separately from the backhaul, by allocating a distinct set of orthogonal radio channels (or sub-channels) for backhaul traffic and for end-user traffic. For example, in an OFDMA system with 24 orthogonal subchannels, 18 subchannels may be reserved for backhauling (ie inter-BS communications) and 6 subchannels may be reserved for end-user delivery (ie BS-SSS or BS-MSS communications). Hereafter, an OFDMA subchannel will be referred to as a channel. Alternatively, end-user traffic and backhaul traffic may share the same channels. In this case, time-slots in a scheduling frame may be pre-allocated for backhaul and end-user traffic.
The Problems
The multi-hop nature of WMNs leads to several technical challenges. Backhaul capacity and scalability are critical requirements for WMNs. To increase backhaul capacity, wireless routers can exploit multiple wireless transceivers, exploiting multiple orthogonal radio channels. However, the design of routing and scheduling algorithms for such networks is challenging. According to the recent survey article by I. Akyiliz et al referenced earlier, ‘These advanced wireless radio technologies all require a revolutionary design in higher-level protocols, especially MAC and routing protocols’.
Currently, there are no backhaul scheduling algorithms for WMNs which have low computational complexity, which can achieve throughputs as high as 100% and which can achieve near-minimal queuing delays, near-minimal delay jitter and near-perfect QoS for all provisioned backhaul traffic flows. A method to schedule multiple guaranteed-rate backhaul traffic flows in uniform single-channel or multi-channel WMNs with up to 100% throughout, with near-minimal delay and jitter and near-perfect QoS is required. A uniform WMN is one where there exists at most one radio edge between a pair of nodes.
Existing WMNs can also suffer from constrained backhaul traffic capacity due to the congestion caused by a small number of gateway BSs. The capacity of a WMN can be increased by adding more gateway BSs, or by adding more radio links to the network in congested areas resulting in a non-uniform WMN. A non-uniform WMN has redundant (extra) radio links between some pairs of nodes, which can be viewed as a single link with a non-uniform (higher) capacity than the other links. A method to schedule multiple guaranteed-rate backhaul traffic flows in non-uniform WMNs with up to 100% throughout, with near-minimal delay and jitter and with near-perfect QoS is required.
In a WMN the BSs typically exploit TDMA, where multiple BSs can access multiple orthogonal radio channels in the time domain. The time-axis consists of many physical time-slots, and a BS with a single radio transceiver can either transmit or receive during one time slot. Two types of conflicts have been identified in the literature. The paper by Min Cao incorporated earlier entitled “Multi-Hop Wireless Backhaul Networks: A Cross-Layer Design Paradigm” defines primary conflicts and secondary conflicts. A ‘Primary’ conflict occurs when one BS with one radio transceiver transmits and receives at the same time. To avoid primary conflicts, the scheduling method must ensure that the number of active radio edges incident to any BS in any time-slot does not exceed the number of radio transceivers available at that node, and that the active directed radio edges incident to each BS are assigned substantially orthogonal (non-conflicting) radio channels in every time-slot. A ‘Secondary’ conflict occurs when the signal power from remote nodes interferes with the signal power at the intended receiver. To mitigate secondary conflicts, the scheduling and channel assignment method must ensure that nearby activated edges do not interference excessively with the intended activated edge. Such schedulers and channel assignment algorithms typically define a conflict graph. Nodes may be represented as vertices, and nodes which may interfere with one another are joined by an edge. In a k-hop interference model, nodes within a distance of K from the primary transmission may interfere with the primary transmission. The following two papers establish that the problem of finding the optimal throughput under a general K-hop WMN interference model is NP-hard: The first paper is by K. Jain et al, entitled “Impact on Interference on Multi-Hop Wireless Networks Performance”, ACM Mobicom 2003, which is hereby incorporated by reference. The second paper is by K. Jain et al, entitled “Impact of Interference on Multi-Hop Wireless Network Performance”, Wireless Networks, 11, pp. 471-487, 2005, which is hereby incorporated by reference.